class Solution {
public:
    vector<vector<int>> arr;
    int dp[75][75][75], flag[75][75][75];
    int dfs(int n, int p1, int p2)
    {
        if (flag[n][p1][p2]) return dp[n][p1][p2];
        if (n >= arr.size()) return 0;
        int ans = -1;
        for (int i = max(p1 - 1, 0); i <= min(p1 + 1, (int)arr[n].size() - 1); i++)
        {
            for (int j = max(p2 - 1, 0); j <= min(p2 + 1, (int)arr[n].size() - 1); j++)
            {
                int temp = arr[n][i];
                if (i != j) temp += arr[n][j];
                ans = max(ans, dfs(n + 1, i, j) + temp);
            }
        }
        flag[n][p1][p2] = 1;
        return dp[n][p1][p2] = ans;
    }
    int cherryPickup(vector<vector<int>>& grid) {
        arr = grid;
        return dfs(1, 0, grid[0].size() - 1) + arr[0][0] + arr[0].back();
    }
};